package 二叉树的最小深度;

import java.util.LinkedList;

/**
 * 二叉树的最小深度
 * 给定一个二叉树，找出其最小深度
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
 * <p>
 * 考查：尝试优先、广度优先
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        int res = getBinTreeMinDepth(node1);
        System.out.println("res = " + res);

        res = getBinTreeMinDepth2(node1);
        System.out.println("res = " + res);

    }

    /**
     * 广度优先
     * 基于队列实现
     *
     * 时间复杂度 O(N)
     * 空间复杂度 O(N)
     */
    private static int getBinTreeMinDepth2(TreeNode root) {
        if (null == root) {
            return 0;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();

        root.deep = 1;
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.pop();

            if (null == node.left && null == node.right) {
                return node.deep;
            }

            if (null != node.left) {
                node.left.deep = node.deep+1;
                queue.offer(node.left);
            }
            if (null != node.right) {
                node.right.deep = node.deep+1;
                queue.offer(node.right);
            }
        }

        return -1;
    }

    /**
     * 深度优先，深度递归
     * 时间复杂度 O(N)
     * 空间复杂度 O(logN)
     */
    private static int getBinTreeMinDepth(TreeNode root) {
        if (null == root) {
            return 0;
        }

        if (null == root.left && null == root.right) {
            // 叶子节点
            return 1;
        }

        // 取左节点深度，没有左节点，返回Integer最大值
        int leftDepth = root.left != null ? getBinTreeMinDepth(root.left) : Integer.MAX_VALUE;
        // 取右节点深度，没有点节点，返回Integer最大值
        int rightDepth = root.right != null ? getBinTreeMinDepth(root.right) : Integer.MAX_VALUE;

        // 取左右节点深度较小的值
        return 1 + Math.min(leftDepth, rightDepth);
    }


    private static class TreeNode {
        int v;
        TreeNode left;
        TreeNode right;
        int deep;

        public TreeNode(int v, TreeNode left, TreeNode right) {
            this.v = v;
            this.left = left;
            this.right = right;
        }
    }
}
